package com.tgy.cmp;

import com.common.sort.tools.Integers;
import com.tgy.Sort;

/**
 * @Author: tgy
 * @Date: 2020-10-15 16:38
 */
public class QuickSort<E> extends Sort<E> {

    private int type;


    public void setType(int type) {
        this.type = type;
    }

    @Override
    protected void sort() {

        if (type == 0) {

            sort(0,elements.length - 1);
        }else if (type == 1) {

            sort01(0,elements.length);
        }
    }

    private void sort(int left,int right) {

        int i = left;
        int j = right;

//        swap(left,left + (int) (Math.random() * (right - left + 1)));

        E base = elements[left];


        while (i <= j)
        {

            while (compare(elements[i],base) < 0) {

                i++;
            }

            while (compare(elements[j],base) > 0) {

                j--;
            }

            if (i <= j)
            {

                swap(i,j);
                i++;
                j--;
            }
        }

        if (left < j) {

            sort(left, j);
        }

        if (i < right) {

            sort(i, right);
        }
    }

    private void sort01(int begin,int end) {

//        badTimeComplexity(begin, end);

//        // 随机选择privot
        swap(begin,begin + (int) (Math.random() * (end - begin)));


        int left = begin,right = end - 1;

        E privot = elements[begin];

        while (left < right) {

            while (left < right) {
                if (compare(privot,elements[right]) < 0) {

                    right--;
                }else {
                    addMoveCount();
                    elements[left++] = elements[right];
                    break;
                }
            }

            while (left < right) {

                if (compare(privot,elements[left]) > 0) {

                    left++;
                }else {

                    addMoveCount();
                    elements[right--] = elements[left];
                    break;
                }

            }
        }

        addMoveCount();
        elements[left] = privot;

        if (left - begin >= 2) {
            sort01(begin,left);
        }

        if (end - (left + 1) >= 2) {
            sort01(left+1,end);
        }
    }

    /**
     * 以下方式时间复杂度有可能为 O(n^2)
     * @param begin
     * @param end
     */
    private void badTimeComplexity(int begin, int end) {
        if (begin >= end) {

            return;
        }

        E privot = elements[begin];

        int left = begin, right = end;

        while (left < right) {

            if (compare(privot,elements[left + 1]) > 0) {

                elements[left] = elements[left + 1];
                left++;
            }else {

                if (compare(privot,elements[right]) <= 0) {

                    right--;
                }else {

                    elements[left] = elements[right];
                    elements[right] = elements[left + 1];
                    left++;
                    right--;
                }
            }
        }

        elements[left] = privot;

        badTimeComplexity(begin,left - 1);
        badTimeComplexity(left + 1, end);
    }
}
